package com.cn.codebrush.数组.回溯;

import java.util.*;

/**
 * @Author Boolean
 * @Date 2022/4/24 14:28
 * @Version 1.0
 */
public class No47全排列II {
    public static void main(String[] args) {
        int[] nums7 = {1,1,2};  //[[1,1,2],[1,2,1],[2,1,1]]
        System.out.println(permuteUnique(nums7));
    }


    static List reslist = new ArrayList();
    public static List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];
        permuteUniqueHelper(nums,new ArrayList(),visited);
        return reslist;
    }

    public static void permuteUniqueHelper(int[] nums,List list,boolean[] visited) {
        if(list.size() == nums.length){
            reslist.add(new ArrayList(list));
            return;
        }

        for(int i=0;i<nums.length;i++){
            if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == true) {
                continue;
            }
            if(visited[i]){continue;}
            visited[i] = true;
            list.add(nums[i]);
            permuteUniqueHelper(nums,list,visited);
            visited[i] = false;
            list.remove(list.size()-1);

        }
    }




    /**
     * 回溯法
     * set去重
     * AC
     */
    static Set resSet = new HashSet();
    public static List<List<Integer>> permuteUnique1(int[] nums) {
        int[] visited = new int[nums.length];
        permuteUniqueHelper1(nums,new ArrayList(),visited);
        return new ArrayList<>(resSet);
    }
    public static void permuteUniqueHelper1(int[] nums,List list,int[] visited) {
        if(list.size() == nums.length){
            resSet.add(new ArrayList<>(list));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(visited[i] == 1){continue;}
            visited[i] = 1;
            list.add(nums[i]);
            permuteUniqueHelper1(nums,list,visited);
            visited[i] = 0;
            list.remove(list.size()-1);
        }
    }
}
